Les processus disposent chacun d'un espace d'adressage protégé inaccessible aux autres processus. Pour communiquer et s'échanger des données, les processus peuvent utiliser des outils de communications offerts par le système. La manipulation de ces outils de communication doit se faire dans le respect de règles de synchronisation qui vont assurer que les données échangées entre les processus restent cohérentes et ne sont pas perdues. Un premier problème de synchronisation est celui de l'accès par un ensemble de processus à une ressource critique , c'est-à-dire une ressource à un seul point d'accès donc utilisable par un seul processus à la fois.

Nous allons mettre en lumière le problème qui peut se poser sur un exemple simple : on considère donc un petit programme de réservation de place (dans un avion, un train, …). 

Ce programme réservation peut être exécuté par plusieurs processus à la fois (autrement dit, le programme est réentrant). La variable nb_place, qui représente le nombre de place restant dans l'avion par exemple, est ici une variable d'état du système (de réservation) On considère l'exécution de deux processus Client_1 et Client_2 (figure 1) : Client_1 est commuté par l' ordonnanceur juste après avoir testé la valeur de la variable nb_place (nb_place = 1). Client_2 s'exécute à son tour, teste nb_place qu'il trouve également égale à 1 et donc effectue une réservation en décrémentant de une unité la variable nb_place. Nb_Place devient égale à 0. Comme le processus Client_2 a terminé son exécution, Client_1 reprend la main. Comme Client_1 avait trouvé la variable nb_place comme étant égale à 1 juste avant d'être commuté, il continue son exécution en décrémentant à son tour nb_place. De ce fait, nb_place devient égale à –1 ce qui est incohérent !!! Une même place a été allouée à deux clients différents !

Fig 1 : Un exemple de concurrence

La variable nb_place doit être accédée par un seul processus à la fois pour rester cohérente : ici en l'occurrence le processus Client_1 qui a commencé la réservation en premier. Nb_Place est donc une ressource critique.

Pour garantir l'exclusion mutuelle, il faut donc entourer l'utilisation de la variable nb_place d'un prélude et d'un postlude. Le prélude prend la forme d'une "protection"qui empêche un processus de manipuler la variable nb_place si un autre processus le fait déjà. Ainsi le processus Client_2 est mis en attente dès qu'il cherche à accéder à la variable nb_place déjà possédée par le processus Client_1. Le postlude prend la forme d'une"fin de protection" qui libère la ressource nb_place et la rend accessible au processus Client_2.

Nous rappelons que le mécanisme sous-jacent au ré ordonnancement des processus peut être la survenue d'une interruption horloge. Aussi une solution pour réaliser l'exclusion mutuelle est de masquer les interruptions dans le prélude et de les démasquer dans le postlude. Ainsi les interruptions sont masquées dès qu'un processus accède à la ressource nb_place et aucun événement susceptible d'activer un autre processus ne peut être pris en compte. Cependant, cette solution est moyennement satisfaisante car elle empêche l'exécution de tous les processus y compris ceux ne désirant pas accéder à la ressource critique . De plus, le masquage et le démasquage des interruptions sont des opérations réservées au mode superviseur et ne sont donc pas accessibles pour les processus utilisateurs. 

Une autre solution est d'utiliser un outil de synchronisation offert par le système : les sémaphores.

Une sémaphore Sem est une structure système composée d'une file d'attente L de processus et d'un compteur K, appelé niveau du sémaphore et contenant initialement une valeur Val. Cette structure ne peut être manipulée que par trois opérations P(Sem), V(Sem) et Init(Sem, Val). Une propriété im port ante de ces opérations est qu'elles sont indivisibles c'est-à-dire que l'exécution de ces opérations ne peut pas être interrompues. Un outil sémaphore peut être assimilé à un distributeur de jetons; l'acquisition d'un jeton donnant le droit à un processus de poursuivre son exécution. 

L'opération INIT a pour but d'initialiser le sémaphore, c'est-à-dire qu'elle met à vide la file d'attente L et initialise avec la valeur Val le compteur K : on définit ainsi le nombre de jetons initiaux dans le sémaphore.

L'opération P(Sem) "attribue un jeton" au processus appelant si il en reste au moins un et sinon bloque le processus dans Sem.L. L'opération P est donc une opération éventuellement bloquante pour le processus élu qui l'effectue. Dans le cas du blocage, il y aura réordonnancement. Concrètement, le compteur K du sémaphore est décrémenté de une unité. Si la valeur du compteur devient négative, le processus est bloqué.

L'opération V(Sem) a pour but de "rendre un jeton" au sémaphore. De plus, si il y a au moins un processus bloqué dans la file d'attente L du sémaphore, un processus est réveille. La gestion des réveils s'effectue généralement en mode FIFO (on réveille le processus le plus anciennement endormi). L'opération V est une opération qui n'est jamais bloquante pour le processus appelant.

La réalisation d'une section critique à l'aide de l'outil sémaphore s'effectue en utilisant un sémaphore MUTEX, dont le compteur K est initialisé à 1. Le prélude de la section critique correspond à une opération P(MUTEX). Le postlude de la section critique correspond à une opération V(MUTEX).

La figure 2 illustre le fonctionnement de la section critique : Client_1 effectue en premier la demande de réservation : le P(Mutex) est passant et le "jeton" est alloué au processus Client_1. Juste après le test de la valeur de Nb_Place, Client_1 perd donc la main ; Client_2 est élu mais le P(Mutex) est bloquant : il n'y a plus de jeton disponible dans le compteur du sémaphore. Comme Client_2 est bloqué, Client_1 reprend la main. Lorsqu'il a achevé sa réservation, Client_1 relâche le jeton par un V(Mutex) : Client_2 est alors réveillé et le jeton lui est attribué.

Fig 2 : Fonctionnement de la section critique